Masala #1053
Karimjon va qismlarga bo`lish
Karimjonga yaqinda sovg`a sifatida uzunligi \(n\) bo`lgan \(A\) butun musbat sonlar massivi sovg`a qilishdi. Karimjon do`sti Asilbek bilan birga o`ynashi uchun ko`proq massivlar kerak, shuning uchun ham u o`zining \(A\) massivini aynan \(k\) ta bo`lakga ajratmoqchi. Bunda har bir bo`lak \(A\) ning qism massivi bo`lishi shart.
Karimjon massivning chiroyliligiga ham e'tibor beradi. Uning fikricha massiv chiroyliligi bu \(X\) ning turli xil tub bo`luvchilari sonidir. Bu yerda esa \(X\) shu massivning barcha elementlari ko`paytmasi. Misol uchun \([2,10,77]\) massivi uchun \(X = 1540\). \(X\) ning turli xil tub bo`luvchilari soni esa \(4\) ta. Demak massiv chiroyliligi \(4\) ga teng.
Karimjon \(A\) massivni shunday \(k\) ta massivga bo`lishga qaror qildiki, hosil bo`lgan massivlar ichida maksimal chiroylilikga ega massiv chiroyliligi minimal bo`lsin. Siz shu qiymatni topishingiz lozim.
Birinchi qatorda ikkita butun son - \(n,k(1 \leq k \leq n \leq 2*10^5)\) \(A\) massiv uzunligi va bo`laklar soni kiritiladi.
Ikkinchi qatorda \(n\) ta butun son - \(A[i](1 \leq A[i] \leq 1000)\) massiv elementlari kiritiladi.
Yagona qatorda bitta butun son, masalaga javobni chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 2 6 7 110 |
3 |
| 2 |
5 1 10 18 19 3 77 |
6 |
1-testda massivni 2 xil usulda bo`lsa bo`ladi.
- Birinchi usul: \([6],[7,110]\). Bunda \(X_1 = 6\) va \(X_2 = 770\). Demak birinchi massiv chiroyliligi \(2\), ikkinchi massiv chiroyliligi esa \(4\). Maksimal qiymatlisi \(4\).
- Ikkinchi usul: \([6,7],[110]\). Bunda \(X_1 = 42\) va \(X_2 = 110\). Demak birinchi massiv chiroyliligi \(3\), ikkinchi massiv chiroyliligi esa \(3\). Maksimal qiymatlisi \(3\).
Ulardan minimali esa \(3\). Demak natija ham \(3\).
Python tilida yozadiganlar uchun: PyPy orqali yechimni yuborish uni tezlashtirishi mumkin!
Telegram kanalimizga obuna bo'ling